#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 1143. 最长公共子序列.py
@time: 2022/1/18 13:19
@desc: https://leetcode-cn.com/problems/longest-common-subsequence/
> 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1. dp
2. Ot(mn), Os(mn)
'''
class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        m, n = len(text1), len(text2)
        # dp[i][j] 表示 text1[0:i-1]与text[0:j-1]的最长公共子序列的长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 当现在两个字符子串最后一位相等，那就是可以+1, 否则就取两者分别去掉最后一位后的长度考察，比如：
                # 遍历到ace, bc的情况，那就要取 ace, b 或者 ac, bc 中公共子序列最长的那个
                dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1] else max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]